//
// Created by 123 on 2024/4/1.
//
/**
 * 简单选择排序
 *      每次挑选最小的元素放在初始位置
 *
 *     更新 n 轮最小位置
 *     即成
 *
 *      O(log n)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);


void simple_selection_sort(Arr &arr);


int main() {
    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    Arr arr = initArray(a, 10);
    simple_selection_sort(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void simple_selection_sort(Arr &arr) {
    for (int i = 0; i < arr->length; ++i) {
        int index = i;
        for (int j = i; j < arr->length; ++j) {
            if (arr->data[index] > arr->data[j])
                index = j;
        }
        if (index != i)
            swap(arr->data[i], arr->data[index]);

    }

}


Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}